package code.c02_list.sqList;

import code.c02_list.sqList.SqListClass;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/9/11 20:37
 * @package code.c02_list.classwork.examples
 * @description 有两个按元素值递增有序的整数顺序表 a 和 b,
 *              设计一个算法将顺序表中 a 和 b 中的全部元素都合并到一个递增有序顺序表 c 中。
 *              采用二路归并的算法。
 */

public class Exam_2_6 {
    public static SqListClass<Integer> merge2(SqListClass<Integer> a, SqListClass<Integer> b) {
        SqListClass<Integer> c = new SqListClass<>();
        int i = 0;
        int j = 0;
        // 当两个表均没有遍历完成时
        while (i < a.size() && j < b.size()) {

            if (a.getElem(i) < b.getElem(j)) {
                // 将较小的a中的元素添加到c中
                c.add(a.getElem(i++));
            } else {
                // 将较小的b中的元素添加到c中
                b.add(b.getElem(j++));
            }
        }
        // 如果a没有遍历完毕
        while (i < a.size()){
            c.add(a.getElem(i ++));
        }

        // 如果b没有遍历完毕
        while (j < b.size()){
            c.add(b.getElem(j++));
        }

        return c;
    }
}
